import collections

# class Solution(object):
#     def minStickers(self, stickers, target):
#         """
#         :type stickers: List[str]
#         :type target: str
#         :rtype: int
#         """
#         d = collections.Counter(target)
#         target_id = {key: i for i, key in enumerate(d.keys())}
#         len_target = len(d)
#         target_list = [0] * len(d)
#         for key in d:
#             target_list[target_id[key]] = d[key]
#         target_tuple = tuple(target_list)
#         total_set = set()
#
#         def add(a, b):
#             out = [0] * len_target
#             total = len_target - b.count(0)
#             count = 0
#             for i in range(len_target):
#                 if b[i] > 0 and a[i] >= target_tuple[i]:
#                     count += 1
#                 out[i] = a[i] + b[i]
#             if count == total:
#                 return False
#             return tuple(out)
#
#         def convert(s):
#             c = collections.Counter(s)
#             out = [0] * len_target
#             for key in c:
#                 if key in d:
#                     total_set.add(key)
#                     out[target_id[key]] = c[key]
#             return tuple(out)
#
#         def judge(a, b):
#             for i in range(len_target):
#                 if a[i] < b[i]:
#                     return False
#             return True
#
#         n = len(stickers)
#         new_sitckers = set()
#         for i in range(n):
#             s = convert(stickers[i])
#             flag = True
#             for key in new_sitckers:
#                 if judge(key, s):
#                     flag = False
#                     break
#             if flag:
#                 new_sitckers.add(s)
#         stickers = list(new_sitckers)
#         n = len(stickers)
#         if len(total_set) != len_target:
#             return -1
#         now_set = set()
#         for i in range(n):
#             if judge(stickers[i], target_tuple):
#                 return 1
#             now_set.add(stickers[i])
#         index = 1
#         while True:
#             index += 1
#             next_set = set()
#             for key in now_set:
#                 for i in range(n):
#                     value = add(key, stickers[i])
#                     if value:
#                         if judge(value, target_tuple):
#                             return index
#                         next_set.add(value)
#             now_set = next_set
import functools


class Solution(object):
    def minStickers(self, stickers, target):
        """
        :type stickers: List[str]
        :type target: str
        :rtype: int
        """
        m = len(target)

        @functools.cache
        def search(mask):
            if mask == 0:
                return 0
            res = m + 1
            for sticker in stickers:
                left = mask
                stack = collections.Counter(sticker)
                for i, c in enumerate(target):
                    if stack[c] and ((left >> i) & 1):
                        stack[c] -= 1
                        left = left ^ (1 << i)
                if left < mask:
                    res = min(res, search(left) + 1)
            return res
        res = search((1 << m) - 1)
        if res > m:
            return -1
        else:
            return res

data = Solution()
stickers = ["with", "example", "science"]
target = "thehat"
print(data.minStickers(stickers, target))
stickers = ["ac", "bb", "acd"]
target = "abbcd"
print(data.minStickers(stickers, target))
stickers = ["indicate", "why", "finger", "star", "unit", "board", "sister", "danger", "deal", "bit", "phrase", "caught",
            "if", "other", "water", "huge", "general", "read", "gold", "shall", "master", "men", "lay", "party", "grow",
            "view", "if", "pull", "together", "head", "thank", "street", "natural", "pull", "raise", "cost", "spoke",
            "race", "new", "race", "liquid", "me", "please", "clear", "could", "reply", "often", "huge", "old", "nor"]
target = "fhhfiyfdcwbycma"
print(data.minStickers(stickers, target))
